1. Technical Field
The invention relates in general to digital circuit design and specifically to the design of response resolvers for associative memories and parallel processors.
2. Prior Art
Associative or content-addressable memory [is there a distinction?] is memory that is accessed not by the addresses of its memory elements but by the data stored in those elements. When a conventional memory is read, the address lines are used to indicate the memory element whose contents are of interest, and the data stored in that element appear at the memory's data lines. With content-addressable memory, the data itself are used to determine which memory elements respond. The data of interest are applied to the memory, and each memory element whose contents match the data input responds to indicate the match. Moreover, the input data can indicate a set of values (e.g., all numbers between 16 and 23), rather than just a single value, to be matched. It can be seen, then, that with content-addressable memory, more than one memory element can respond to a single request. Unlike conventional memory, in which each element's address is unique, multiple content-addressable memory elements can contain, and therefore respond to, a given data request. This creates the need for a means to determine which memory elements are responding.
Similar considerations arise in the operation of associative parallel processors. Although each element in such systems is not just a memory but also a processor for the manipulation of data, when the processor is addressed by a particular data pattern, multiple processing elements can respond in the same way as multiple content-addressable memory elements. Therefore, parallel processors also require a means of determining which of their elements are responding.
For both content-addressable memories and associative parallel processors, the process of determining which elements are responding is termed response resolution. A response resolver can provide various kinds of information both about whether there are any responders and about their locations in the memory or processor array. For example, in some situations, it is desirable to know the locations of all the responders; in others, it may be necessary to determine the number of responding elements. For either problem, there are solutions in the prior art. To determine responder locations, an iterative approach is typically used. The first step is for the resolver to determine if there are any responders. To do so, it uses a prioritization scheme by which the highest-priority responder can be found and its location determined. Then the resolver temporarily disables that highest-priority responder and repeats the process, determining the location of the next-highest-priority responder. This process is repeated with the remaining responders until none remains. This iterative response resolution can be implemented with the prior art OR-gate chain shown in FIG. 1. Each input on the left side of the chain corresponds to one processing element (PE) and is asserted if that PE is a responder. It can be seen that the output on the right side is asserted only if the PE is a responder and there are no higher-priority responders. In the figure, PE1 is the first responder; it passes a 1 down the chain to inhibit PE2 and lower-priority responders. The bottom of the chain produces a some/none response to indicate whether any PEs are responding. The system can then recognize the PE with an output of 1 as a responder, disable its response, and continue the process until no responders remain, as indicated by a 0 at the bottom of the chain.
Another response-resolution approach is to count the number of responders. The prior art chain of exclusive-or (XOR) gates in FIG. 2 can be used to count responders in log.sub.2 N steps, where N is the length of the chain. The basic procedure is to successively derive the bits of a binary count of the responders by, in each step, determining the exclusive-or of the responders and then disabling one-half of them. The figure shows the three steps of the procedure for a chain of length seven. Initially, in Step 1, there are six responders, and the last gate in the chain produces a 0 as the least significant bit of the count. In the next step, every other responder is disabled, so that three remain and a 1 is the output of the chain. Finally, every other responder is again disabled, and a most significant bit of 1 is produced. The three bits, in reverse order, give 110.sub.2 =6, the number of responders.
Each of these approaches, prioritization and counting, has its uses in various applications. Therefore, it is desirable, especially for integrated-circuit implementations of association memories and processors, to provide the capability to implement either technique. Moreover, it is important that any such implementation be sufficiently simple so as not to occupy a great deal of space on the chip. The invention disclosed here meets these requirements, as described below.